#include <iostream>
#include <vector>
using namespace std;

template<class Comparable>
void printVec(const vector<Comparable>& x){
	for(int val : x)
		cout << val << " ";
	cout << endl;
}

template<class Comparable>
void insertionSort( vector<Comparable> & a ){
	int j;
	for( int p = 1; p < a.size( ); p++ )
	{
		Comparable tmp = a[ p ];
		for( j = p; j > 0 && tmp < a[ j - 1 ]; j-- )
			a[ j ] = a[ j - 1 ];
		a[ j ] = tmp;
		printVec(a); // prints the contents of the vector in order
	}
}

void quickSort( vector<int> & a, int low, int high )
{
	if (low < high)
	{
		int mid = ( low + high )/2; // select pivot to be element in middle position
		int pivot = a[ mid ];
		swap( a[high], a[mid] ); // put pivot in a[high]
		// Begin partitioning
		int i, j;
		for( i = low, j = high - 1; ; )
		{
			while ( a[i ] < pivot ) ++i;
			while( j > i && pivot < a[j ] ) --j;
			if( i < j )
				swap( a[ i++ ], a[ j-- ] );
			else
				break;
		}
		swap( a[ i ], a[ high ] ); // Restore pivot
		printVec(a); // prints the contents of the vector in order
		quickSort( a, low, i - 1 ); // Sort small elements
		quickSort( a, i + 1, high ); // Sort large elements
	}
}

int main(){
	vector<int> x = {11,9,1,5,3,7};
	insertionSort(x);
	
	vector<int> y = {11,9,1,5,3,7};
	quickSort(y, 0, 5);
}
